Current trends in computing suggest that computers are becoming networked to one another on a greater and greater scale. For example, computers that previously were connected to other computers in the same building over a local-area network (LAN) are now commonly connected to other computers all over the world over a wide-area network (WAN), an intranet, or the Internet. The rising prominence of the Internet in fact presages a future where all computers are able to connect with one another over a single vast global network.
With this rise in connectivity comes the need for greater scalability in directory services for such networks. One type of directory is similar to a phone book. The phone book permits a person to look up the phone number of another person so that the first person can communicate with the second person. Similarly, this type of directory for a computer network permits a computer user to look up the electronic address of another computer user (for example, the user's current dynamic Internet Protocol (IP) address in the case of a typical home Internet user), so that the first user can communicate with the second user. Although directory services may be used for a wide variety of different applications other than just to locate a user by looking up his or her electronic address, such user-location applications are nevertheless very common. For example, being able to determine the current IP address of a computer user is a very important feature for such diverse Internet applications as Internet telephony, whiteboarding, and videoconferencing.
However, unlike the phone book, which is a static directory, the directory for a computer network such as the Internet frequently must be dynamic in order to be useful. The phone book is a static directory in that it is not updated very often, typically only once a year when a new book is published. The phone book remains accurate, however, because each person's phone number generally also does not change very often. Conversely, in the case of the Internet, while every user may have a static electronic mail address (that is, an e-mail address that does not change often), every user typically does not have a static IP address. Dial-up users in particular are assigned a dynamic IP address by their Internet Service Provider (ISP) each time they initiate an online session. This lessens the accuracy and usefulness of a static directory for many Internet applications.
Static directory services nevertheless do exist for the Internet, and other Internet-like networks. One such static directory service is provided by the Lightweight Directory-Access Protocol (LDAP). The LDAP is known within the art, a version of which is specifically described in W. Yeong, et al., Request for Comments (RFC) 1777, March 1995, which is hereby incorporated by reference. The LDAP permits a server to maintain a static directory. Clients capable of communicating with the server are able to add entries to the directory by sending the server the appropriate request. These entries are static in that they persist until the client establishing them requests their removal from the server. If clients forget to make such requests, the server may maintain their entries in the directory indefinitely, which in time may result in the directory including outdated information. For example, if the server is maintaining a user-location directory of IP addresses, an entry containing the dynamic IP address of a client who has since logged off the Internet is inaccurate.
Dynamic directory services differ from static directory services in that entries must be periodically refreshed by their clients, or otherwise they automatically are removed by the server. Dynamic directory services also exist for the Internet, and other Internet-like networks. One such dynamic directory service is provided by the User Location Service (ULS). The ULS is known within the art, and is specifically described in R. Williams, Internet Draft "draft-uls-1.txt", February 1996, which is hereby incorporated by reference. A server maintaining a dynamic directory as provided by the ULS is receptive to requests from clients to add entries to the directory that include a time-to-live value set by the client. If the client does not refresh its entry before the time-to-live value times out, the server is permitted to delete the entry. Thus, if the server is maintaining a user-location directory of IP addresses, an entry containing the dynamic IP address of a client who has since logged off will eventually be deleted by the server.
Dynamic directories are useful in that they permit the servers maintaining them to periodically perform a garbage collection operation in a manner which does not affect the directories' accuracy. An entry in a dynamic directory is dynamic in that it lives for only a given period of time unless refreshed by its client. The server thus only deletes expired entries. By comparison, servers maintaining static directories perform garbage collections indiscriminately, because they do not know which entries have expired. The servers may delete only very old entries, which probably are outdated, but this means the entries will have persisted long enough to have rendered the directories inaccurate for a period of time. Alternatively, the servers may delete relatively younger entries, in which case the accuracy of the directory is maintained but some accurate entries will likely have been deleted.
Dynamic directories have their own flaws, however. One significant problem with dynamic directories is scalability. For example, a server may have sufficient bandwidth and processing power to maintain ten-thousand clients refreshing entries having time-to-live values of five minutes. Because the clients themselves set the time-to-live values of their entries, however, the server may be incapacitated if the ten-thousand clients have instead set the time-to-live value of their entries to only five seconds. The server may also be incapacitated if there are one-million clients, instead of only ten-thousand, even if all the clients set the time-to-live value of their entries to five minutes. This scalability problem is especially dramatic in the case of the Internet, where a server cannot know a priori the number of clients that may add an entry to the server's directory, nor the time-to-live value of those entries.
Dynamic directories thus suffer from a problem that does not afflict static directories. A static directory is likely not to become incapacitated because if more entries are added than its server can handle, the server will likely just force a garbage collection to delete the oldest entries so that new ones may be added. A dynamic directory does not have this alternative, since its server can only delete expired entries. Moreover, the client for an entry of a static directory likely only contacts the server twice--first to add the entry, and second to remove the entry--while the client for an entry of a dynamic directory must contact the server periodically to refresh its entry. The main reason that static directories are more scalable is that they generally do not have to service periodic refresh requests, as dynamic directories do. This greater server load is another factor implicated in the scalability problem besieging dynamic directories.
There is a need, therefore, to solve this scalability problem. Such a solution should permit servers to maintain dynamic directories regardless of their bandwidth or processing power. That is, the solution should permit the servers to handle client refreshes in dynamic directories without becoming incapacitated.